#include "arbolbmas.h"

template<class Key, class Record>
ArbolBMas<Key, Record>::ArbolBMas(const std::string& nombreArchivo, u_int32_t tamanioNodo) : raiz(tamanioNodo){
    this->tamanioNodo = tamanioNodo;
    raiz.setNodeNumber(0);

    if (archivo.open(nombreArchivo, tamanioNodo)) {
        open = true;
        raiz = leerNodo(0);
    } else {
        open = archivo.create(nombreArchivo, tamanioNodo);
    }
}

template<class Key, class Record>
ArbolBMas<Key, Record>::~ArbolBMas(){
}

template<class Key, class Record>
bool ArbolBMas<Key, Record>::isOpen(){
    return open;
}

template<class Key, class Record>
Node<Key, Record> ArbolBMas<Key, Record>::leerNodo(u_int32_t pos){
    //std::cout << "ArbolBMas<Key, Record>::leerNodo..." << std::endl;
    Node<Key, Record> nodo(tamanioNodo);
	archivo.read(pos, nodo);
    nodo.setNodeNumber(pos);
    return nodo;
}

template<class Key, class Record>
void ArbolBMas<Key, Record>::escribirNodo(Node<Key, Record>& nodo){
    //std::cout << "ArbolBMas<Key, Record>::escribirNodo..." << std::endl;
    archivo.write(nodo.getNodeNumber(), nodo);
}

template<class Key, class Record>
void ArbolBMas<Key, Record>::agregarNodo(Node<Key, Record>& nodo){
    u_int32_t pos = archivo.append(nodo);
    nodo.setNodeNumber(pos);
}

template<class Key, class Record>
Nullable<Record> ArbolBMas<Key, Record>::buscar(Key clave){
    Node<Key, Record> nodo = raiz;
    while (! nodo.isLeave()){
        u_int32_t pos = nodo.getDescendant(clave);
        nodo = leerNodo(pos);
    }
    Nullable<TreeRecord<Key, Record> > result = nodo.get(clave);
    Nullable<Record> record;
    if (result)
        record.set(result.get().getData());
    return record;
}

template<class Key, class Record>
bool ArbolBMas<Key, Record>::modificar(Record registro){
    Node<Key, Record>& nodo = raiz;
    Node<Key, Record>& padre = raiz;
    u_int32_t pos = 0;
    while (! nodo.isLeave()){
        pos = nodo.getDescendant(registro.getKey());
        padre = nodo;
        nodo = leerNodo(pos);
    }
    bool modificado;
    try {
        modificado = nodo.update(registro);
    } catch (ContainerFullException& e){
        manejarOverflow(nodo, padre, registro);
        modificado = true;
    }
    return modificado;
}

template<class Key, class Record>
bool ArbolBMas<Key, Record>::borrar(Key clave) {
    Node<Key, Record> nodo = raiz;
    u_int32_t pos = 0;
    while (! nodo.isLeave()){
        pos = nodo.getDescendant(clave);
        nodo = leerNodo(pos);
    }
    bool borrado = nodo.remove(clave);
    if (borrado){
        if (nodo.getSizeUsed() < nodo.getCapacity() / 2) {
            //TODO
        }
        escribirNodo(nodo);
    }
    return borrado;
}

template<class Key, class Record>
bool ArbolBMas<Key, Record>::insertar(Record registro){
    Nullable<TreeRecord<Key, Record>> nullable;
    TreeRecord<Key, Record> treeRec(true);
    treeRec.setData(registro);
    nullable.set(treeRec);

    return insertarRecursivo(raiz, raiz, nullable);
}

template<class Key, class Record>
bool ArbolBMas<Key, Record>::insertarRecursivo(Node<Key, Record>& nodo, Node<Key, Record>& padre,
                                               Nullable<TreeRecord<Key, Record> >& registro){
    bool success = false;

    if (! nodo.isLeave()) {
        u_int32_t posHijo = nodo.getDescendant(registro.get().getKey());
        Node<Key, Record> hijo = leerNodo(posHijo);
        success = insertarRecursivo(hijo, nodo, registro);
    }

    if (registro) {
        try {
            //std::cout << "Agregar Registro..." << std::endl;
            success = nodo.add(registro.get());
            if (success) {
                //std::cout << "Entre Agregar Registro..." << std::endl;
                escribirNodo(nodo);
                //std::cout << "Salgo Agregar Registro..." << std::endl;
            } //else
                //std::cout << "Dio false el add..." << std::endl;
        } catch (ContainerFullException& e) {

            manejarOverflow(nodo, padre, registro);

            if (registro && &raiz == &nodo) {
                u_int16_t nivel = raiz.getLevel() + 1;
                u_int32_t nodoDerecho = registro.get().getRightNode();

                raiz = Node<Key, Record>(tamanioNodo);
                raiz.setNodeNumber(0);
                raiz.setLevel(nivel);
                raiz.add(registro.get());
                raiz.setRightNode(nodoDerecho);
                escribirNodo(raiz);

                registro.unset();
            }

            return ! registro;
        }
    }
    registro.unset();

    return success;
}

template<class Key, class Record>
void ArbolBMas<Key, Record>::manejarOverflow(Node<Key, Record>& nodo, Node<Key, Record>& padre,
                                             Nullable<TreeRecord<Key, Record> >& registro) {

    if (! distribuir(nodo, padre, registro))
        dividir(nodo, registro);

}

template<class Key, class Record>
bool ArbolBMas<Key, Record>::distribuir(Node<Key, Record>& nodo, Node<Key, Record>& padre,
                                        Nullable<TreeRecord<Key, Record> >& registro) {

    if (nodo.getNodeNumber() == 0)
        return false;

    auto it = padre.find(registro.get().getKey(), false);
    auto end = padre.getRecords().end();

    bool aDerecha = it != end;
    it = aDerecha ? ++it : --it;
    u_int32_t posHermano = it == end ? padre.getRightNode() : (*it).getLeftNode();
    if (aDerecha) it--;

    Node<Key, Record> hermano = leerNodo(posHermano);

    TreeRecord<Key, Record> regAMover = aDerecha ? nodo.getRecords().back() : nodo.getRecords().front();
    bool isSameRecord = aDerecha
            ? regAMover.getKey() < registro.get().getKey()
            : regAMover.getKey() > registro.get().getKey();
    if (isSameRecord)
        regAMover = registro.get();

    uint32_t tamRegAMover = BinaryStream::sizeOf(regAMover);
    uint32_t tamReg = isSameRecord ? 0 : BinaryStream::sizeOf(registro.get());
    bool canMove = (hermano.getSizeUsed() + tamRegAMover <= hermano.getCapacity())
            && (isSameRecord || nodo.getSizeUsed() - tamRegAMover + tamReg <= nodo.getCapacity());

/*
    if (! canMove && ! nodo.isLeave()) {
        std::cerr << "MR " << tamRegAMover << std::endl;
        std::cerr << "SB " << hermano.getSizeUsed() << " " << hermano.getCapacity() << std::endl;
        std::cerr << hermano.toString() << std::endl;
        std::cerr << "ND " << nodo.getSizeUsed() << " " << nodo.getCapacity() << std::endl;
        std::cerr << nodo.toString() << std::endl;
    }
*/

    if (canMove) {
        Key promotionKey = regAMover.getKey();

        if (! nodo.isLeave()){
            if (aDerecha) {
                u_int32_t aux = nodo.getRightNode();
                nodo.setRightNode(regAMover.getLeftNode());
                regAMover.setLeftNode(aux);
                regAMover.setRightNode(hermano.getRecords().front().getLeftNode());
            } else {
                regAMover.setRightNode(regAMover.getLeftNode());
                regAMover.setLeftNode(hermano.getRightNode());
            }
            regAMover.setKey((*it).getKey());
        }

        hermano.add(regAMover);
        if (! isSameRecord) {
            nodo.remove(promotionKey);
            nodo.add(registro.get());
        } else if (! aDerecha && ! nodo.isLeave()){
            nodo.add(registro.get(), true);
            nodo.remove(registro.get().getKey());
        }

        if (nodo.isLeave() && ! aDerecha)
            promotionKey = nodo.getRecords().front().getKey();

        TreeRecord<Key, Record> promoted(false);
        promoted.setKey(promotionKey);
        promoted.setLeftNode(aDerecha ? nodo.getNodeNumber() : hermano.getNodeNumber());
        promoted.setRightNode(aDerecha ? hermano.getNodeNumber() : nodo.getNodeNumber());
        registro.set(promoted);

        escribirNodo(hermano);
        escribirNodo(nodo);
        it = it == end ? --it : it;
        padre.remove((*it).getKey());

        return true;
    } else {
        return false;
    }
}


template<class Key, class Record>
void ArbolBMas<Key, Record>::dividir(Node<Key, Record>& nodo, Nullable<TreeRecord<Key, Record> >& registro) {

    Node<Key, Record> nuevoNodo(tamanioNodo);
    nuevoNodo.setLevel(nodo.getLevel());
    nuevoNodo.setRightNode(nodo.getRightNode());

    nodo.add(registro, true);

    Nullable<Key> clave;
    auto registros = nodo.empty();
    registros.back().setRightNode(nodo.getRightNode());

    Node<Key, Record>* parte = &nodo;
    for (auto it = registros.cbegin(); it != registros.cend(); ++it){
        auto reg = *it;

        if (! clave && parte->getSizeUsed() + BinaryStream::sizeOf(reg) > parte->getCapacity() / 2) {
            if (parte->isLeave()) {
                parte->add(reg);
                reg = *(++it);
            } else {
                parte->setRightNode(reg.getLeftNode());
            }
            clave.set(reg.getKey());
            parte = &nuevoNodo;

            if (! parte->isLeave())
                continue;
        }

        parte->add(reg);
    }

    agregarNodo(nuevoNodo);
    if (nodo.isLeave())
        nodo.setRightNode(nuevoNodo.getNodeNumber());

    if (nodo.getNodeNumber() == 0)
        agregarNodo(nodo);
    else
        escribirNodo(nodo);

    TreeRecord<Key, Record> promoted(false);
    promoted.setKey(clave);
    promoted.setLeftNode(nodo.getNodeNumber());
    promoted.setRightNode(nuevoNodo.getNodeNumber());
    registro.set(promoted);
}

template<class Key, class Record>
void ArbolBMas<Key, Record>::toString(u_int32_t pos, std::stringstream& sout, u_int16_t nivel) {
    //std::cout << "Leo nodo: " << pos << "..." << std::endl;
    Node<Key, Record> nodo = leerNodo(pos);
    //std::cout << "Leido: " << pos << "..." << std::endl;

    sout << std::string(nivel, '\t') << pos << "] " << nodo.toString() << std::endl;
    if (! nodo.isLeave()){
        for (TreeRecord<Key, Record> reg : nodo.getRecords()){
            toString(reg.getLeftNode(), sout, nivel+1);
        }
        if (nodo.getRightNode())
            toString(nodo.getRightNode(), sout, nivel+1);
        else
            sout << "WARN " << nodo.toString() << std::endl;
    }
}

template<class Key, class Record>
std::string ArbolBMas<Key, Record>::toString() {
    std::stringstream sout;
    toString(0, sout, 0);
    return sout.str();
}
